package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月28日
*时间：下午4:07:40
*/
public class Q60 {
    /** 
     * param A : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
    public int searchInsert(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int left = 0;
        int right = A.length - 1;
        int point = 0;
        while (left <= right) {
            point = (right + left) / 2;
            if (A[point] > target) {
                right = point - 1;
            } else if (A[point] == target) {
                return point;
            } else {
                left = point + 1;
            }
        }
        return A[point] > target ? point : point + 1;
    }

    @Test
    public void testA() {
        int[] A = { 1, 3, 5, 6 };
        int target = 7;
        System.out.println(searchInsert(A, target));
    }
}
